RMS on The Connection (NPR show)
...but the GNU operating system was first conceived in 1983, as the crowning achievment of the GNU project. So, yes, RMS did think of it first - when Linus was still in grade school.
Not to slam on Linus; he did come up with mostly the same idea independently. It's yet another case of "great minds think alike". But Linux is possible today because of the pioneering work done by RMS & Co.
HURD was supposed to be the last step in the progression, but for some reason the project faltered. Linus and Linux stepped in to fill that last gap, such that Linux (or, at least, Debian GNU/Linux) is the fulfillment of that goal.