The wikipedia article on "Newline" traces the choice of NL as a line terminator (or separator) to Multics in 1964; unfortunately the article has few citations to sources but there is no reason to doubt this is correct. I suspect it was chosen because the space saving obtained by using a single character outweighed the costs of translating to the two-character CR-LF sequence when doing input and output.

The main alternative, CR-LF, originates in the control codes used to physically move the paper carriage on a teletype machine, where CR would return the carriage to its home position, and LF would rotate the paper roller to move the print position down one line. The two control characters appear in the ITA2 code which dates back to 1924 and which is apparently still in use (see Wikipedia); apparently ITA2 took them from the Murray variant of Baudot code which dates to 1901.

For younger readers it is worth noting that in the mainframe tradition, there was no newline character; rather a file was a sequence of records which were either fixed length (often 80 characters, based on punched cards) or variable length; variable length records were typically stored with a character count at the start of each record. If you have a mainframe file consisting of a sequence of variable length records each containing arbitrary binary content, converting this losslessly to a UNIX-style file can be a tricky conversion.

Linux, of course, was just a re-implementation of Unix, and Unix took many of its design decisions from Multics, so it looks like the key decision was made in 1964.

The wikipedia article on "Newline" traces the choice of NL as a line terminator (or separator) to Multics in 1964; unfortunately the article has few citations to sources but there is no reason to doubt this is correct. There are two obvious benefits to this choice over CR-LF: space saving, and device independence.

The main alternative, CR-LF, originates in the control codes used to physically move the paper carriage on a teletype machine, where CR would return the carriage to its home position, and LF would rotate the paper roller to move the print position down one line. The two control characters appear in the ITA2 code which dates back to 1924 and which is apparently still in use (see Wikipedia); apparently ITA2 took them from the Murray variant of Baudot code which dates to 1901.

For younger readers it is worth noting that in the mainframe tradition, there was no newline character; rather a file was a sequence of records which were either fixed length (often 80 characters, based on punched cards) or variable length; variable length records were typically stored with a character count at the start of each record. If you have a mainframe file consisting of a sequence of variable length records each containing arbitrary binary content, converting this losslessly to a UNIX-style file can be a tricky conversion.

Linux, of course, was just a re-implementation of Unix, and Unix took many of its design decisions from Multics, so it looks like the key decision was made in 1964.