Krishna's last visit to Islamabad in 2010 had ended on a sour note after the then Foreign Minister Shah Mahmood Qureshi launched a stunning tirade against him.
In its report, the Tribune said the new visa agreement would "deliver the first ever tangible results of a nascent peace process between the arch rivals that had stalled following the 2008 Mumbai attacks."
The News daily reported Krishna had "sent out positive vibes" by telling the media soon after his arrival that India believed in a stable and prosperous Pakistan.
The two countries resumed their peace process last year after a gap of over two years following the brazen assault on India's financial hub in November 2008 by operatives of the Pakistan-based Lashkar-e-Tayiba.
Indian sources said terrorism and the prosecution of Pakistanis involved in the Mumbai incident had figured "in great detail" in Foreign Secretary Ranjan Mathai's talks with his Pakistani counterpart Jalil Abbas Jilani.
The Pakistani media, however, focused on the new visa regime and other agreements for cultural exchanges between the Indian Council for Cultural Relations and the Pakistan National Council of the Arts and for allowing visits of pilgrims across the Line of Control in Jammu and Kashmir.
The new visa regime will introduce tourist visas for the first time and include visas on arrival for people aged over 65 years.
Group tourist visas will be issued to 10 or more people who apply through registered tour operators and multiple-city visas valid for a year will be issued to businessmen.
The liberalised regime will include five new categories of visas while retaining several old ones, like the category for diplomatic visas.
The new visa regime had been finalised for signing during a meeting of the home and interior secretaries in May but had to be put off due to opposition from Pakistan's Interior Minister Rehman Malik, who wanted it to be inked at the political level.
Malik told reporters on Friday that a decision to sign the pact was made when President Zardari met Prime Minister Manmohan Singh on the margins of the NAM Summit in Tehran recently.
Pakistan Foreign Secretary Jilani said he and his Indian counterpart had had "positive and fruitful discussions on all aspects including Jammu and Kashmir."
Krishna meets Khar, pushes for justice for 26/11 victims
India must look at issues 'unemotionally': Khar
Krishna will have to SHOW his serious intent to Pak
Abundant patience needed in dealing with Pak: Krishna
Krishna-Khar meet: Terror, Pak's 26/11 trial on agenda