We present the results of optical (R-band) photometric and polarimetric monitoring and Very Long Baseline Array imaging of the blazar S4 0954+658, along with Fermi γ-ray data during a multi-waveband outburst in 2011 March-April. After a faint state with a brightness level R ~ 17.6 mag registered in the first half of 2011 January, the optical brightness of the source started to rise and reached ~14.8 mag during the middle of March, showing flare-like behavior. The most spectacular case of intranight variability was observed during the night of 2011 March 9, when the blazar brightened by ~0.7 mag within 7 hr. During the rise of the flux, the position angle of the optical polarization rotated smoothly over more than 300°. At the same time, within 1σ uncertainty, a new superluminal knot appeared with an apparent speed of 19.0 ± 0.3c. We have very strong evidence that this knot is associated with the multi-waveband outburst in 2011 March-April. We also analyze the multi-frequency behavior of S4 0954+658 during a number of minor outbursts from 2008 August to 2012 April. We find some evidence of connections between at least two additional superluminal ejecta and near-simultaneous optical flares.