Although Pleurostomum was described almost a century ago, flagellates assigned to this taxon have been recorded only in very occasional faunistic studies of highly saline habitats, and their phylogenetic position has remained uncertain. We report the cultivation, ultrastructure, and phylogenetic relationships of Pleurostomum flabellatum isolated from a Korean saltern pond of 313 per thousand salinity. This isolate is biflagellated with a cytostomal groove, and is not distinguishable from previous accounts of P. flabellatum from saturated brines in India and Australia. Pleurostomum flabellatum shows ultrastructural features characteristic of many Heterolobosea: (1) a striated rhizoplast, (2) an absence of stacked Golgi bodies, (3) parallel basal bodies and flagella, and (4) a large number of peripheral microtubules supporting a rostrum. 18S rRNA gene phylogenies strongly confirm the affinities of P. flabellatum within Heterolobosea. Furthermore, the 18S rRNA gene of P. flabellatum has the heterolobosean-specific helix 17_1, and a group I intron in the same position as in Acrasis rosea. Within Heterolobosea, the 'amoeboflagellate' genera Naegleria and Willaertia were its closest relatives with high bootstrap support and posterior probability. P. flabellatum was observed only as a flagellate, and never as an amoeba. Since light microscopy and electron microscopy observations indicate that P. flabellatum flagellates are capable both of feeding and division, there might be no amoeba stage. Being morphologically distinct from its closest relatives and phylogenetically distant from other flagellate-only Heterolobosea, P. flabellatum cannot be moved into any previously described heterolobosean genus. Instead, we move Pleurostomum into Heterolobosea, and assign as the type species Pleurostomum salinum Namyslowski 1913, a species that closely resembles P. flabellatum. The optimal temperature for growth of P. flabellatum is 40 degrees C. Interestingly, P. flabellatum grows optimally at 300 per thousand salinity and fails to grow below 200 per thousand salinity, indicating that it is an 'extreme halophile'. The optimal salinity for growth is the highest for any eukaryote examined to date.