Le prime notizie sulla chiesa risalgono al 6 giugno 1607, quando fu letta nel Senato di Genova una supplica del Capitano di Polcevera, che a nome di molti Sestresi, chiedeva l'autorizzazione per la costruzione di una nuova chiesa.

Il 3 ottobre 1610, de licentia et ordine del Vicario Generale, il sac. Gaspare Carabello di Luca piantava la croce sul sito scelto per l'erigenda chiesa e l'indomani 4 ottobre 1610, Giovanni Battista Dario arciprete della cattedrale di S.Lorenzo, poneva la prima pietra (arch. di S.G. Battista - Notaio Gio Batta Delfino); da un documento ufficiale del 24 ottobre 1618 risulta che la grandiosa chiesa era terminata. Durante la costruzione funzionava già una piccola cappella. L'8 giugno 1620 Mons. Felice Tamburelli, Vicario Generale, benediceva la nuova chiesa e vi celebrava la prima S.Messa. Il 21 luglio 1620 ne fu chiesta, e poch mesi dopo ottenuta, l'erezione a parrocchia in autonomia.

Dopo anni di rivalità con la parrocchia di San Giovanni Battista, ad essa preesistente, il 3 febbraio 1623 l'arcivescovo De Marini dichiarava smembrate e indipendenti le due chiese ed elevava la nuova a parrocchia autonoma, nominando due rettori.

Nel 1624 veniva costruita la torre campanaria. La chiesa fu consacrata il 10 ottobre 1629 da Mons. Vincenzo Spinola vescovo di Brugnato. Il 24 maggio 1672 l'arcivescovo Giovanni Battista Spinola, in visita pastorale, la dichiara Chiesa insigne e le conferisce il titolo di Arcipretura. Nel 1951 la chiesa fu insignita da Pio XII con il titolo di Basilica Minore.

Progettista della chiesa si ritiene che fosse il comasco, scultore e architetto, Rocco Pellone al quale si deve anche il bellissimo altare maggiore e il tabernacolo, desinati originariamente a S.Lorenzo in Genova: un'unica navata orienta da nord a sud, cosa inconsueta per quei tempi, quando le absidi erano sempre poste a est, ma obbligata dall'ubicazione, in prossimità della riva del mare, per proteggere l'entrata principale dalle mareggiate.

Una costruzione grandiosa (larga 18,50 metri e lunga 37,50, alta al cornicione 14 metri e, prolungata con il presbierio di altri 17 metri) e dalla concezione architettonica ardita, a causa della quale la leggenda narra che il progettista si sia tolto la vita al momento di togliere la ponteggiatura della volta, temendone il crollo.

Molti artisti lavorarono alla decorazione della chiesa, da Giulio Benso, autore dello stupendo affresco dell'Assunta al centro della volta, a Domenico Fiasella, a Domenico Piola fino a Nicolò Barabino e i suoi discepoli; e molto si prodigarono per l'Assunta i sestresi, come testimoniano le origini di alcuni altari come quello ora dedicato alla Madonna della Salute, un tempo altare di S.Francesco, scelto come protettore dai "canapini" o fabbricanti di cordame, e quello della cappella di S.Pietro, che apparteneva alla Compagnia dei Marinai.

Ma soprattutto la chiesa è vissuta sull'impegno e l'amore dei suoi parroci, che nel corso dei secoli hanno provveduto ad abbellire e conservare questo gioiello architettonico; fra tutti si ricorda in particolare don Bartolomeo Cassinoide, cui si devono gli ultimi restauri di tutti gli affreschi dell'interno, riportati all'antico splendore.