Tree to 20 m tall; bark rough on part of trunk, flaky above, branches smooth. Juvenile leaves sessile, opposite for few pairs, scabrous above and below, then alternate, becoming glabrous, ovate; adult leaves petiolate, alternate, ovate to elliptic or lanceolate, oblique, 7–15 cm long, 2–5.5 cm wide, concolorous, glossy, green; reticulation usually sparse, with obscure island oil glands. Inflorescences axillary, unbranched; peduncles stout, to 0.5 cm long, 7–9(–11)-flowered; buds sessile, ovoid to oblong, strongly warty, to 0.9 cm long, 0.6 cm diam., no scar (single operculum); operculum conical to hemispherical; stamens irregularly flexed; anthers dorsifixed, reniform to cordate; ovules in 2 vertical rows; flowers white. Fruit sessile, hemispherical to truncate-globose, to 0.9 cm long, 1.4 cm diam.; disc raised-annular or raised-convex; valves 4 or 5, rim level or strongly exserted; seed black or brown, smooth, pyramidal but distorted by one curved face, hilum terminal. Flowers Feb.–Apr.
Sometimes included in the widespread E. baxteri, but distinguished from that species by the stringy bark that does not fully extend up the trunk, thicker-textured adult leaves and buds that are more strongly warted. Eucalyptus victoriana is one of three species stringybark eucalypts endemic to the Grampians. The other two species (E. verrucata and E. serraensis) are distinguished from E. Victoriana by the smoother stems (that often lack stringy bark altogether), often fewer and more strongly warted buds (in clusters of 1, 3 or 7), and larger fruits.
