Судя по медали Маттео де Пасти, датированной юбилейным 1450 годом, на которой был изображен новый храм, проект Альберти предполагал радикальную перестройку церкви. В первую очередь намечалось с трех сторон сделать новые фасады, а затем возвести новый свод и хор, перекрытый большим куполом.

Альберти получил в свое распоряжение весьма ординарную провинциальную церковь – приземистую, со стрельчатыми окнами и широкими стрельчатыми арками капелл, с простой стропильной кровлей над главным нефом. Он задумал превратить ее в величественный мемориальный храм, способный соперничать с древними святилищами. Монументальный фасад в форме двухъярусной триумфальной арки имел очень мало общего с привычным обликом итальянских церквей. Просторная купольная ротонда, открывавшаяся посетителю в глубине сводчатого зала, пробуждала воспоминания о постройках древнего Рима.

К сожалению, замысел Альберти был осуществлен только отчасти. Строительство затянулось. Главный фасад храма так и остался незавершенным, а то, что в нем было сделано, не совсем точно соответствовало первоначальному проекту.

Одновременно со строительством «Храма Малатесты» в Римини по проектам Альберти возводилась церковь в Мантуе. Маркиз Мантуанский, Лодовико Гонзага, покровительствовал гуманистам и художникам.

Когда в 1459 году Альберти появился в Мантуе в свите папы Пия II, он встретил у Гонзага очень теплый прием и сохранил дружеские отношения с ним до конца своей жизни. Тогда же Гонзага поручил Альберти составить проект церкви Сан-Себастьяно. Оставшись в Мантуе после отъезда папы, Альберти в 1460 году закончил модель новой церкви, строительство которой было поручено флорентийскому архитектору Луке Фанчелли, находившемуся при мантуанском дворе. По меньшей мере еще дважды, в 1463 и 1470 годах, Альберти приезжал в Мантую, чтобы следить за ходом работ, вел переписку по этому поводу с маркизом и Фанчелли.