The story
First appears c. 1969. Derives from US military intelligence and CIA documents, in news coverage of the Green Beret Case, and further popularized in the movie Apocalypse Now (1979). A play on the term terminate with prejudice when an employee’s employment is terminated, meaning will not rehire employee to same position in future (i.e., prejudiced against rehiring), hence terminate definitively, i.e., kill.
Etymology from Wiktionary, CC BY-SA 4.0.