The men, aged 20 and 32, were hit on their legs and thighs as they sat drinking and chatting with friends near the monument in Weston Park, opposite the Children's Hospital, last night.
The gunman fired up to 15 air rifle pellets at the group, hurling homophobic insults and shouting at them to leave the park.
A police officer called to the incident, which happened at around 10.45pm, was also shot at as he spoke to the victims.
He escaped uninjured but reported one pellet narrowly missing his head.
The police helicopter was scrambled and officers on foot launched a hunt for the gunman who fled into nearby Crookes Valley Park.
Police stepped up patrols in the park and pledged to meet representatives of Sheffield's gay community to discuss the attack.
Chief Superintendent Jon House, responsible for the area, said branded the shooting "a despicable attack".
"This was clearly a homophobic attack where the people injured heard insulting homophobic language being used as the offender opened fire," he said.
"There were a group of men sitting and chatting in Weston Park, which is a well-known public sex environment when they heard shots being fired towards them and homophobic insults aimed at them.
"We will not tolerate any attacks on any sections of the community and are determined to catch this offender, who clearly put innocent members of the community and police officers at risk with his indiscriminate shooting.
"I am seeking a meeting with representatives of the gay community to explain what we plan to do to ensure this person is caught because it will obviously come as a shock to a lot of people."
Paramedics treated the injured men, whose skin was broken by the pellets, at the scene.
Steve Slack, director for the Centre for HIV and Sexual Health in Sheffield, said: "Homophobic bullying in any form is unacceptable and this was a despicable attack on two innocent individuals.
"The centre is working very closely with the police and other organisations across Sheffield to educate people and to try and eradicate this behaviour.
"Fortunately, in our experience, this is something that the police do take very seriously, and we would encourage anyone who is subjected to any form of homophobic bullying to contact the police immediately."
The man police are hunting was seen in the park with another man and a woman pushing a pram.
He was white, aged 25 to 30, of slim to medium build and had short blonde hair. He was wearing a dark T-shirt and jeans.
The gun attack came two nights after a civilian police community support officer was shot at when she confronted a gang shooting at birds in Bolton-on-Dearne.
Members of the Safer Neighbourhood Team were investigating reports of a gang roaming around armed with air weapons when they found five youths, two of whom were shooting at birds in the River Dearne.
The gang was ordered to stop firing and one yob opened fire, aiming at one officer.
Sgt Derek Barker, who covers Barnsley, said: "Air rifles can kill - people have died from injuries inflicted by air rifles. They are not toys but are potentially lethal weapons and anyone deliberately firing an air rifle at an individual is committing a serious offence."
Anyone with information about the Weston Park attack should call the volume crime team at Ecclesfield police station on 0114 296 3910 or Crimestoppers on 0800 555111.
Information can also be passed on confidentially by visiting http://www.safeinsouthyorks.co.uk/