Definitely mediums....based on your boot size you will have no problem fitting into them. Put your boots into the binding while on the board and adjust the toe and ankle strap to fit accordingly. The cartels (and most bindings) have a significant amount of adjustment to the straps to allow for good boot fit. I have size 10.5 boots and have 2012 medium cartels mounted on my Never Summer Sl . They fit great and are a great all mountain binding.