We report the discovery of a new radio galaxy within the location error box of the gamma-ray source 3EG J1735-1500. The galaxy is a double-sided jet source forming a large angle with the line of sight. Optical observations reveal a V ~ 18 magnitude galaxy at the position of the radio core. Although the association with the EGRET source is not confirmed at the present stage, because there is a competing, alternative gamma-ray candidate within the location error contours which is also studied here, the case deserves further attention. The new radio galaxy can be used to test the recently proposed possibility of gamma-ray emitting radio galaxies beyond the already known case of Centaurus A.