W połowie lat 1990-tych Tłocznia Metali Pressta rozpoczęła prace nad nowymi wersjami niekierowanych pocisków rakietowych M-21 do polowego systemu rakietowego BM-21 ”Grad”, w tym z głowicami typu cargo i o zwiększonej donośności. W 1996 r. Pressta nawiązała w zakresie opracowania pocisku M-21 o wydłużonym zasięgu współpracę ze, specjalizującą się w projektowaniu i produkcji silników rakietowych, francuską firmą Celerg. We wrześniu 1997 r. TM Pressta S.A. oraz Celerg podpisały umowę regulującą zakres współpracy, która dotyczyła współdziałania przy wyprodukowaniu prototypu zmodernizowanego pocisku rakietowego.

Pierwsze próby poligonowe nowych rakiet, które nazwano ”Feniks” (czasami spotyka się nazwę ”Phenix”), odbyły się w Polsce latem 1998 r. We wrześniu 1998 r. były eksponowane na VI Międzynarodowym Salonie Przemysłu Obronnego w Kielcach. 17.10.1998 r. odpalono w ramach badań na poligonie w Swiętoszowie pierwszy pocisk skompletowany w Polsce. Wobec zainteresowania wojska kontynuacją prac, obie firmy podpisały w lutym 1999 r. umowę przedwstępną, formułującą ogólnie podział wdrożenia na fazy certyfikacji i produkcji seryjnej oraz podział zadań pomiędzy partnerów. W dniu 8.07. 1999 r. doszło do podpisania umowy o współpracy przemysłowej i handlowej, szczegółowo określającej zakres i harmonogram współpracy zarówno w fazie wdrożenia jak i produkcji seryjnej. Na mocy umowy, kadłuby silników miano dostarczać do Francji, gdzie przeprowadzana miała być ich elaboracja materiałem pędnym (początkowy udział polskich zakładów w produkcji silnika wynosił początkowo 13%). Pressta odpowiadać miała za montaż finalny pocisku z elementów dostarczonych przez krajowych i zagranicznych kooperantów.

Jesienią 1999 r. rozpoczęto proces certyfikacji ”Feniksa”. Program prób zakończono w sierpniu 2001 r. W tej ich fazie badano wyłącznie rakiety z głowicami odłamkowo-burzącymi. Wyniki prób były bardzo dobre. W 2002 r. rozpoczęto uzupełniające badania ”Feniksa” z głowicą typu "cargo" Hesyt, eleborowaną subamunicją kumulacyj-no-odłamkową GKO. W marcu 2003 r. odbyły się komisyjne badania zdawczo-odbiorcze partii próbnej pocisków M-21FK ”Feniks-Z”, po których nastąpiło pierwsze zamówienie MON na te pociski, opiewające na 450 rakiet. W dalszych latach MON zamawiał także wyłącznie pociski z głowicą typu cargo. Firma oferuje trzy odmiany pocisków rodziny Feniks: z głowicą odłamkowo-burzącą (M-21 FHE), z głowicą typu cargo z subamunicją kumulacyjno-odłamkową (M-21 FK) oraz z głowicą typu cargo z minami przeciwpancernymi (M-21 FK1). Od 2003 r. do końca 2008 r. Fabryka Produkcji Specjalnej Sp z o.o. wyprodukowała kilka tysięcy pocisków M-21FK ”Feniks”.