NYT opinion piece by a former deputy director of the CIA (5 August 2016)
On 5 August 2016 the New York Times posted an opinion piece by former deputy director of the CIA Michael J. Morell. It contained the following paragraph:
In the intelligence business, we would say that Mr. Putin had recruited Mr. Trump as an unwitting agent of the Russian Federation.
This paragraph follows a number of observations of then candidate Trump's actions in public. While it's not a substantiated mention in that it provides compelling evidence (though you might that's a bit subjective), it doesn't claim to have some sort of smoking gun, it does clearly link Trump and Russia.
Steele dossier (reported 31 October 2016)
One of the early accusations were made in the Steele dossier. Wikipedia has an extensive page on that. This is a more elaborate claim than the one in the NYT opinion piece because it claims to have statements from sources with knowledge of the situation. The describe it as follows:
The Trump–Russia dossier, also known as the Steele dossier, is a private intelligence report written from June to December 2016 containing allegations of misconduct and conspiracy between Donald Trump's presidential campaign and the Government of Russia during the 2016 election. The dossier comprises 17 memos based on reports from unnamed sources known to the author, counterintelligence specialist Christopher Steele, a former head of the Russia Desk for British intelligence (MI6), written for the private investigative firm Fusion GPS.
The Wikipedia article also includes an extensive section on when and how it was released to the public (there's also a part on the use by others privately, but that seems outside the scope of your question). According to the Wikipedia page (which in turn is referenced from news reports), the dossier was first disclosed to reporters:
Hints of existence
Jane Mayer has described how, in "late summer, Fusion set up a series of meetings, at the Tabard Inn, in Washington, between Steele and a handful of national-security reporters.... Despite Steele's generally cool manner, he seemed distraught about the Russians' role in the election." Mayer attended one of the meetings. No news organizations ran any stories about the allegations at that time.
On 31 October 2016, the Steele report was reported on by Mother Jones magazine, according to Wikipedia:
By October 2016, Steele had compiled 33 pages (16 memos), and he then passed on what he had discovered to David Corn, a reporter from Mother Jones magazine. On October 31, 2016, a week before the election, Mother Jones reported that a former intelligence officer, whom they did not name, had produced a report based on Russian sources and turned it over to the FBI.
That would be this article entitled "A Veteran Spy Has Given the FBI Information Alleging a Russian Operation to Cultivate Donald Trump".
