Bayesian optimal sensor placement, in its full generality, seeks to maximize the mutual information between uncertain model parameters and the predicted data to be collected from the sensors for the purpose of performing Bayesian inference. Equivalently, the expected information entropy of the posterior of the model parameters is minimized over all possible sensor configurations for a given sensor budget. In the context of structural dynamical systems, this minimization is computationally expensive because of the large number of possible sensor configurations. Here, a very efficient convex relaxation scheme is presented to determine informative and possibly-optimal solutions to the problem, thereby bypassing the necessity for an exhaustive, and often infeasible, combinatorial search. The key idea is to relax the binary sensor location vector so that its components corresponding to all possible sensor locations lie in the unit interval. Then, the optimization over this vector is a convex problem that can be efficiently solved. This method always yields a unique solution for the relaxed problem, which is often binary and therefore the optimal solution to the original problem. When not binary, the relaxed solution is often suggestive of what the optimal solution for the original problem is. An illustrative example using a fifty-story shear building model subject to sinusoidal ground motion is presented, including a case where there are over 47 trillion possible sensor configurations. The solutions and computational effort are compared to greedy and heuristic methods.