The Irish News had criticised Robinson and Deputy First Minister Martin McGuinness for refusing to release details of the cost of the trip, or the reason behind it.
The paper, which is Northern Ireland's biggest selling daily, said McGuinness's Sinn Féin party eventually released a document outlining the background to the trip, but Robinson's Democratic Unionist Party continued to refuse to divulge any information.
Irish News reporters had questioned why the pair were staying in hotels which they say cost the taxpayer £650 per night, on a trip that they say was "secrecy-shrouded", had no clear purpose, and for which no itinerary was revealed.
The editor of The Irish News, Noel Doran, said it was "remarkable that the person who is effectively our prime minister should be urging a boycott of the best-selling Northern Ireland-based paper simply for asking legitimate questions about the spending of tax-payers' money.
"Mr Robinson set off on an ambitious and publicly-funded trip to south and north America but refused to say who was in the travelling party, where they were staying and what was their itinerary.
"A range of news organisations covered the story, and made repeated and unsuccessful enquiries about the costs involved, but the considered response of the first minister was: 'Stop reading The Irish News.'"
The National Union of Journalists' executive council said Robinson's comments were "clearly irresponsible", and called for him to withdraw them immediately.
Robinson's comments also led to outrage online, including widespread criticism by Twitter users who said the episode would only encourage them to read the paper more. Some reported shortages on newsstands after readers responded to Robinson's comments by buying multiple copies.
The DUP has responded by issuing a statement claiming Robinson's comments were clearly "in good humour", and denying he called for a boycott. The statement also said the episode was "a further pathetic attempt by the Irish News to draw attention to itself", and argued that "any sensible person who watched the UTV clip will know this is a concocted story".
The Irish Times reports that the First Minister's relationship with The Irish News has been "distinctly testy" ever since the paper reported on the affair that Robinson's wife, Iris, was having with a 19-year-old man.