We present efficient online learning algorithms that eschew projections in favor of linear optimizations using the Frank-Wolfe technique. We obtain regret bounds that vary from the optimal $\tilde{O}(\sqrt{T})$ for stochastic online smooth convex optimization to $\tilde{O}(T^{3/4})$ for general online convex optimization. Besides the computational advantage, other desirable features of our algorithms are that they are parameter-free in the stochastic case and produce sparse decisions.