In an ideal transmission line, yes. Varying Zo is called dispersion, and comes with losses or change in velocity factor.
Lossless stripline traces are such an example. Practical coax is very close indeed. (Note that coax and stripline are effectively the same thing, on a basic level: an inner conductor surrounded by an outer conductor, with dielectric between; the shapes of the conductors is irrelevant to propagation below waveguide cutoff.) Practical stripline on FR-4 is pretty good up to a GHz or so, and notably lossy near or above there; special low-loss dielectrics are available to solve that if required.
Microstrip traces are a counterexample. Even if the dielectric is lossless, there are two additional effects: 1. the wave partly propagates in air above the board, at higher velocity factor; 2. the wave has a nonzero component at infinity, i.e., it radiates (which is also a loss component with respect to the intended propagation along the trace). The amount of radiation from practical microstrip is normally quite small (parts per thousand?), small enough we can ignore it for digital signal quality purposes (and that substrate and conductor losses are much worse than radiation), and small enough that, at typical signal levels (a few volts for single-ended CMOS, used usually below 100MHz or so; or fractional volts for differential e.g. LVDS and such, up to 10s of GHz), the radiation is near or below acceptable levels, even for a bare unshielded board.
Note that losses don't necessarily cause dispersion; when dielectric and conductor losses are balanced, a wave (e.g. step change in voltage) remains together, and just attenuates over distance. Typically, conductor loss is worse, and dispersion does occur (consider coax, with the modestly-low resistance copper conductors, but extremely low loss PE dielectric, or even foamed PTFE, or (mostly) air for special hardline types); this can be balanced with loading coils at regular intervals (which reduce velocity and increase Zo, such that the reactive and resistive aspects of the line are brought into equal proportion), which is basically how the first transatlantic telegraph cables, and later for voice and data, were designed -- such a long route cannot preserve even slow (hand-tapped) Morse code with a plain coax design, but with loading coils integrated, bandwidth is extended to, ~kHz at least, with I think the last analog cables topping out at 10MHz or so. (By the 1980s, only fiber-optic cables were being installed, which still contain repeater amplifiers and various frequency compensation tricks, but the fidelity is generally much better, and the bandwidth far greater of course.)
Tim