We propose a method of simulating efficiently many-body interacting fermion lattice models in trapped ions, including highly nonlinear interactions in arbitrary spatial dimensions and for arbitrarily distant couplings. We map products of fermionic operators onto nonlocal spin operators and decompose the resulting dynamics in efficient steps with Trotter methods, yielding an overall protocol that employs only polynomial resources. The proposed scheme can be relevant in a variety of fields such as condensed-matter or high-energy physics, where quantum simulations may solve problems intractable for classical computers.