Nel 1882, Selim-Girei Tevkelev, che nel 1865 fu nominato Mufti di Orenburg, si rivolse al ministro dell'interno Dmitry Tolstoy presentando la richiesta di costruire una moschea a San Pietroburgo, richiesta che venne accolta. Solo nel 1906 il ministro permise però la creazione di un apposito comitato, presieduto da Ahun Ataulla Bayazitov, che aveva l'obiettivo di raccogliere 750.000 rubli entro 10 anni per la costruzione della moschea. Il comitato organizzò raccolte di denaro nelle città e province russe, anche attraverso lotterie e cartoline con l'immagine della futura moschea, e ricevette donazioni da innumerevoli sponsor. Il maggior donatore fu 'Said Abd al-Ahad Khan, Emiro di Bukhara, il quale si occupò di tutte le spese per l'effettiva costruzione della moschea.

Inizialmente il luogo scelto per la costruzione della moschea era un sito di proprietà dell'ingegnere Dolotsky, situato su un lato della capitale, lungo Kronversky Avenue. Successivamente ci si rese conto che però lo spazio non era sufficiente, e la posizione non era ottimale. La decisione definitiva fu quindi in favore di un sito più accessibile, lungo Kronverksky Prospekt, nel pieno centro della città: la cupola azzurra della moschea è infatti perfettamente visibile dal ponte della Trinità che attraversa la Neva. Il permesso per costruire in questo sito fu concesso dall'Imperatore Nicola II 3 luglio 1907. Quell'autunno il comitato incaricato della costruzione della moschea approvò il progetto dell'architetto Nikolai Vasilyevich Vasilyev e dell'ingegnere Stepan Krichinsky; la supervisione della costruzione fu inoltre affidata all'accademico Alexander von Hohen.

Il 16 febbraio 1910[1] si svolse la cerimonia della posa della pietra di fondazione. Questa data fu scelta per commemorare il 25º anno del regno di 'Said Abd al-Ahad Khan a Bukhara, in seguito al fatto che, durante il regno di Alexander III, l'Asia centrale si stava unendo alla Russia.[2] L'apertura della moschea fu invece programmata per l'anno 1913, per commemorare il trecentesimo anniversario della dinastia Romanov. Si tratta però solo di una data ufficiale: la finitura degli interni proseguì successivamente ancora per diversi anni, fino al 1920[3], quando l'edificio fu definitivamente completato.[1]

Ahun Bayazitov presiedette la cerimonia della posa; a questa parteciparono innumerevoli ospiti illustri, appartenenti a istituzioni religiose e al governo. Tra questi, Mohammed Alim Khan, l'ambasciatore dell'Impero ottomano e della Persia, e Tevkelev, leader del partito musulmano nella Duma.

Il luogo destinato alla posa era circondato da una recinzione e su di essa era costruita una tenda a cupola, il cui lato orientale confinava con la fondazione già eretta. Lì vicino, su un tavolo, c'erano un martello d'argento, una pala, una tavola con iscrizioni russe e arabe e diversi pezzi di mattoni di marmo bianco.[1]

Nel 1940 le autorità sovietiche vietarono di tenere cerimonie religiose all'interno della moschea, e trasformarono l'edificio in un deposito di materiale medico. Nel 1956 Sukarno, primo presidente dell'Indonesia, che si era recato a San Pietroburgo in visita, fece richiesta ufficiale che la moschea fosse restitutita alla comunità musulmana; la sua richiesta venne accolta 10 giorni dopo.[4]

Nel 1980 la moschea fu in buona parte restaurata.