We study distributionally robust optimization (DRO) with Sinkhorn distance---a variant of Wasserstein distance based on entropic regularization. We provide convex programming dual reformulation for a general nominal distribution. Compared with Wasserstein DRO, it is computationally tractable for a larger class of loss functions, and its worst-case distribution is more reasonable. We propose an efficient first-order algorithm with bisection search to solve the dual reformulation. We demonstrate that our proposed algorithm finds δ-optimal solution of the new DRO formulation with computation cost Õ(1/δ³) and memory cost Õ(1/δ²), and the computation cost further improves to Õ(1/δ²) when the loss function is smooth. Finally, we provide various numerical examples using both synthetic and real data to demonstrate its competitive performance and light computational speed.