El Palyam se estableció en abril de 1945 como la décima compañía del Palmaj (Pluga Yud) de donde se originó en el Pelotón Naval del Palmach.
[1] El primer comandante de la compañía fue Abraham Zakai, que pertenecía al Cuarto Batallón, adscrito al batallón del Estado mayor del Palmaj.
Desde agosto de 1945 hasta mayo de 1948, aproximadamente 70 miembros del Palyam escoltaron a 70.000 inmigrantes en 66 viajes por mar, desde el Reino de Suecia en el norte, hasta Argelia en el sur; Francia al oeste hasta Rumanía en el este.
La unidad tenía instalaciones en el kibutz Neve Yam, en los campamentos de refugiados judíos ubicados en Eretz Israel, y en las localidades de Givat Hashlosha, Shefayim y Yagur.
La mayoría de oficiales navales durante los primeros años posteriores a la fundación del Estado de Israel, eran veteranos del Palyam.