Excessive use of let a problem in Clojure?
First of all, you could use abstract structural binding (a.k.a. destructuring) to reduce the number of let bindings:

(defn- create-counts_org [[_ &amp; present :as coll]]
  "Computes how many times did each 'next state' come from a 'previous state'.
   The result type is {previous_state {next_state count}}."
  (let [zipped  (map vector coll present)
        sorted  (sort zipped)
        grouped (group-by first sorted)
        seconds (map (fn [[key pairs]] [key (map second pairs)]) (seq grouped))
        freqs   (map (fn [[key secs]]  [key (frequencies secs)]) seconds)]
    (into {} freqs)))


I think there's nothing wrong in using let bindings that are technically not necessary to improve readability and comprehensibility. 

But in your function, I think it is pretty clear what every step does: 


sorted -> the first thing I see is the sort function
grouped ->  the first thing I see is the group-by function
seconds / freqs -> I think these are also pretty clear, using second and frequencies 


And because each let binding just uses the previous binding once, I would probably use the thread-last (-&gt;&gt;) macro:

(defn- create-counts [[_ &amp; rest :as coll]]
  "Computes how many times did each 'next state' come from a 'previous state'.
   The result type is {previous_state {next_state count}}."
  (-&gt;&gt;  (map vector coll rest)
        (sort)
        (group-by first)
        (map (fn [[key pairs]] [key (map second pairs)]))
        (map (fn [[key secs]]  [key (frequencies secs)]))
        (into {})))


I think this also answers your better to just put it all inside one expression question. Also, even if there where a performance penalty in using let bindings, it would probably be negligible.