W maju 1968 roku podjęto decyzję o rozpoczęciu w zakładach GosMBK "Wympieł" (ГосМКБ «Вымпел») prac rozwojowych nad nowym pociskiem rakietowym oznaczonym jako E-155MP. Projekt został oznaczony zgodnie z przyjętą w zakładzie nomenklaturą, jako K-33, kolejny z serii po K-13 i K-23.
Jeszcze w 1968 roku zbudowano dwa prototypy, które zostały skonstruowane w układzie "kaczki" w celu zapewnienia możliwości wystrzeliwania z tych samych wyrzutni co R-40.
W 1972 roku przebudowano trzy samoloty do roli latających laboratoriów, które miały za zadanie przetestować poszczególne elementy pocisku. MiG-25 posłużył jako platforma badawcza do testów odpalania, MiG-21 do testowania głowicy naprowadzającej i Tu-104, którego zadaniem było przetestowanie nowego radaru ze skanowaniem fazowym ZBI-16 Zasłon i jego współpracy z systemem naprowadzającym pocisku.
thumb|Schemat rakiety R-33 Równocześnie prowadzono prace badawcze nad czterema rodzajami systemów naprowadzających dla pocisku R-33: półaktywnej głowicy radiolokacyjnej, aktywnej głowicy radiolokacyjnej, głowicy termicznej i kombinowanej termiczno/radiolokacyjnej.