Designing efficient mechanisms for Virtual Machine (VM) provisioning and allocation is a major challenging problem that needs to be solved by cloud providers. We formulate the VM provisioning and allocation problem in clouds as an integer program and design truthful greedy mechanisms that solve it. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to lie about their requested bundles of VM instances and their valuations. We perform extensive experiments in order to investigate the performance of the proposed mechanisms.