Pierwszy kościół w tym miejscu został zbudowany z drewna w roku 797 i poświęcony św. Wiktorowi[1]. W jego fundacji czynnie uczestniczyły szlacheckie rody Artigeri e degli Scoparii. Drugi kościół został zbudowany w 947 roku przez Moisè Veniera i dedykowany jego świętemu patronowi, Mojżeszowi. Świątynia ta została odnowiona po drugim pożarze z 1105 roku[1]. U zarania swych dziejów kościół San Moisè powiązany był raczej z chrześcijaństwem wschodnim (bizantyńskim) niż łacińskim; jego pierwszy proboszcz, Christoforo, był z pochodzenia Grekiem, a i starotestamentowa dedykacja (podobnie jak w przypadku kilku innych kościołów Wenecji) również budziła skojarzenia z chrześcijaństwem Wschodu[2].

Obecny kościół powstał w rezultacie przebudowy z 1632 roku[1]. Konieczność przebudowy była spowodowana degradacją techniczną materiału budowlanego, ale zdaniem historyka Flaminia Correra, mogła też mieć związek ze wzrostem religijności, spowodowanej zarazą z lat 1630–1631; była również nawiązaniem do pewnego wątku z życia Mojżesza, kiedy uratował swój lud przed plagą jadowitych węży[2]. Prace nad odbudową fasady rozpoczęły się w 1668 roku według projektu Alessandra Tremignona i ostatecznie kosztowały 30 tysięcy dukatów, wyłożonych przez rodzinę Finich i Vincenza Finiego, który w 1687 roku został prokuratorem San Marco i którego popiersie znalazło się na szczycie centralnego obelisku na fasadzie kościoła[1].